今天我們要來談談另外兩個很常見的線性資料結構：Queue 和 Stack。Queue 的概念就是先進先出啦！就像是排隊買東西，當然先來的人要讓他先買囉！而 Stack 則是先進後出，例如我們把一堆書給疊起來，當別人要拿書的時候，勢必得從最上面那本開始拿起囉！通常 Queue 可以應用在排程，例如當我們程式有很多工作要做的時候，就可以把要做的事情先放到 Queue 裡面，當有空的時候就從 Queue 裡面把最早的待做工作拿出來做。而 Stack 因為是最後放入的，也就是最新的會被先拿出來，所以可以應用在像是需要回朔復原的場景，就可以一路從最新的慢慢往舊的去復原囉！而我們之前也在遞迴的時候提到，當一個 Function call 另一個 Function 時，一些原 Function 的狀態跟返回點就會存在記憶體中的 Stack，所以假使當我們一路 Call 了很多 Function，就可以透過 Stack 一路返回到最初開始的 Function 囉！
在 Queue 一般來說會有兩種操作：enqueue 是把元素放進 Queue，而 dequeue 則是拿出來。在 Stack 則是 push 把元素放進 Stack，而 pop 是把最新的拿出來。那就讓我們來看看這四個語言分別怎麼運用 Stack 跟 Queue 吧！
class Queue:
def __init__(self):
self.queue = []
def dequeue(self):
char = self.queue[0]
self.queue = self.queue[1:]
return char
def enqueue(self, char):
self.queue.append(char)
class Stack:
def __init__(self):
self.stack = []
def pop(self):
return self.stack.pop()
def push(self, char):
self.stack.append(char)
s = input()
my_stack = Stack()
my_queue = Queue()
for i in s:
my_stack.push(i)
my_queue.enqueue(i)
is_palindrome = True
for i in range(len(s) // 2):
if my_stack.pop() != my_queue.dequeue():
is_palindrome = False
break
if is_palindrome:
print(f"The word {s} is palindrome")
else:
print(f"The word {s} is not palindrome")
class Queue 裡頭只有一個 attribute queue，是個 List 讓我們來當作 Queue 使用，至於要如何讓 List 表現得像是 Queue，這裡 Implement 兩個 method，dequeue 和 enqueue。enqueue 就是把元素放入 Queue 之中，這裡我們很簡單地用了 List 的 append。而 dequeue 就是把最早放入 list 的元素取出來，這裡用了 List 的 Slicing，也就是把第一個元素取出來後，透過 Slicing 把第二個元素之後的 List 當作更新後 Queue。再來看到 Stack 的部分，也就是 class Stack，其中也是有一個 stack 的 Attribute，用了一個 List 來當 Stack。而 Stack 有兩個 Method，pop 和 push。push 實際上也是直接利用 List 的 append，而 pop 是要把最後放入的元素取出，我們可以直接用 List 的 pop()，預設是直接刪除最後一個元素。這樣子我們就簡單實作完 Queue 跟 Stack 啦！dequeue 和 pop 分別取出字元並判斷是否相同，假使有一次判斷不相同，則不可能是 Palindrome，概念上就是從頭跟尾把字元取出來做比對，直到比到中間都相同 (這是為什麼我們要 for i in range(len(s) // 2))，那就是 Palindrome 囉！scala.collection.immutable.Stack) 以及 Mutable (scala.collection.mutable.Stack) 的 Stack class，不過 Immutable 版本的 Stack 在官方文件已經不建議使用，因為可以直接使用 List 來替代。至於 mutable Stack 的用法跟其語言差不多，也是自帶了 pop 以及 push 這兩個方法。來看下面例子，雖然這是個 Mutable 的 Stack (mutable.Stack[Char]())，但是仍然可以用 val，因為 val mutableChars 不能被修改的部分是指不能被 Reassign，但本身指向的 Stack 的內容是可以修改的。Stack[Char]() 中括號內的 Char 是類型參數，表示這個 Stack 裡頭資料的類型是 Char，也是所謂的 Generic class (之後會細談)。除了 push，pop，還有像是 size，isEmpty，top (秀出最新被 Push 進 Stack 的值但不取出) 等等。至於 Immutable Stack 我們就直接使用 List，例如下面程式中的 val chars 是個 List of Char，如果要模擬出 push 那麼就可以直接把新的元素 Prepend 在 List 的最前頭，也就是 'a' :: chars。要模擬出 pop 的話，則用 newChars.head 來得到最新 Prepend 的元素，而用 newChars.tail 來得到除了最新元素的 List。import scala.collection.mutable.Stack
// Mutable stack
val mutableChars = Stack[Char]()
mutableChars.push('a')
mutableChars.push('b')
println(mutableChars.pop()) // b
println(mutableChars.pop()) // a
// Immutable stack
val chars = List[Char]('b', 'c')
val newChars = 'a' :: chars
println(newChars.head) // 'a'
println(newChars.tail) // List('b', 'c')
import scala.collection.mutable.Queue，而 Queue 本身也自帶了 enqueue 和 dequeue 兩種常見的方法，所以用起來跟其他語言是差不多的，至於 Immutable 的 Queue，則是 import scala.collection.immutable.Queue，用起來也是類似，只是每次在 enqueue 之後會得到一個新的 queue，而 dequeue 則會得到 (<Dequeue 後的值>, <Dequeue 後新的 Queue>) 這個 Tuple 囉！import scala.collection.mutable.Queue
val queue = Queue[Char]()
queue.enqueue('a')
queue.enqueue('b')
println(queue)
println(queue.dequeue)
println(queue.dequeue)
package main
import "fmt"
type Queue struct {
queue []string
}
func (q *Queue) enqueue(str string) {
q.queue = append(q.queue, str)
}
func (q *Queue) dequeue() string {
v := q.queue[0]
q.queue[0] = ""
q.queue = q.queue[1:]
return v
}
type Stack struct {
stack []string
}
func (s *Stack) push(str string) {
s.stack = append(s.stack, str)
}
func (s *Stack) pop() string {
v := s.stack[len(s.stack)-1]
s.stack[len(s.stack)-1] = ""
s.stack = s.stack[:len(s.stack)-1]
return v
}
func main() {
ptrQ := Queue{queue: []string{}}
ptrQ.enqueue("a")
ptrQ.enqueue("b")
fmt.Println(ptrQ.dequeue())
fmt.Println(ptrQ.dequeue())
ptrS := Stack{stack: []string{}}
ptrS.push("a")
ptrS.push("b")
fmt.Println(ptrS.pop())
fmt.Println(ptrS.pop())
}
enqueue 和 pop 的實作都是把新元素透過 append 加上 Slice 之中。 dequeue 則是先把第一個元素取出之後並在之後返回，另外用 Slicing 留下第二個元素之後當作新的 Queue。pop 也是類似概念，只不過我們要留下的是除了最後一個元素之外的所有元素。dequeue 或 pop 的話，會引發 panic: runtime error: index out of range 唷！那就要用到我們先前提到關於 Error handling 的部分。留給大家去思考看看囉！struct Queue {
queue: Vec<i32>,
}
struct Stack {
stack: Vec<i32>,
}
impl Queue {
pub fn new() -> Queue {
Queue {
queue: Vec::new(),
}
}
pub fn enqueue(&mut self, value: i32) {
self.queue.push(value);
}
pub fn dequeue(&mut self) -> Result<i32, &str> {
if !self.queue.is_empty() {
Ok(self.queue.remove(0))
}
else {
Err("The queue is empty!")
}
}
}
impl Stack {
pub fn new() -> Stack {
Stack {
stack: Vec::new(),
}
}
pub fn push(&mut self, value: i32) {
self.stack.push(value);
}
pub fn pop(&mut self) -> Result<i32, &str> {
let len = self.stack.len();
if !self.stack.is_empty() {
Ok(self.stack.remove(len - 1))
}
else {
Err("The stack is empty!")
}
}
}
fn main() {
let mut queue = Queue::new();
queue.enqueue(1);
queue.enqueue(2);
println!("{}", queue.dequeue().unwrap());
println!("{}", queue.dequeue().unwrap());
let mut stack = Stack::new();
stack.push(1);
stack.push(2);
println!("{}", stack.pop().unwrap());
println!("{}", stack.pop().unwrap());
}
Vector 來實作。Vector 是可變長度的 Array。再來就是為 Queue 實作 enqueue 和 dequeue 這兩個方法，而實務上就是去操作 Vector，直接使用 Vector 的 push 及 remove 的方法。至於 Stack 的部分，幾乎與 Queue 是類似的，只差在 remove 的時候我們是取出最後一個被 Push 的資料囉！
iThome鐵人賽
看影片追技術